package leetcode_61_80;

import java.util.ArrayList;
import java.util.List;

public class subsets_78 {
    /**
     *给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     *
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        /**
         * 思路是递归回溯
         * 0ms ,100%
         */
        ans.add(new ArrayList<>());
        function(nums,0);
        return ans;
    }
    List<Integer>combine=new ArrayList<>();
    List<List<Integer>>ans=new ArrayList<>();
    /**
     * 递归回溯求所有组合
     * @param i   当前递归起始数字
     */
    public void function(int[] nums,int i){
        if(i==nums.length){
            return;
        }
        for (int t = i; t < nums.length; t++) {
            combine.add(nums[t]);
            ans.add(new ArrayList<>(combine)); //每次往下经过一个节点，直接添加进结果集
            function(nums, t+1);
            combine.remove(combine.size()-1);
        }
    }
}
